/*!
 * # [1146.快照数组](https://leetcode.cn/problems/snapshot-array/description/)
 *
 * @lc app=leetcode.cn id=1146 lang=rust
 *
 * algorithms
 * Medium (32.86%)
 * Likes:    102
 * Dislikes: 0
 * Total Accepted:    8.4K
 * Total Submissions: 25.6K
 * Testcase Example:  '["SnapshotArray","set","snap","set","get"]\n[[3],[0,5],[],[0,6],[0,0]]'
 *
 * ## 描述
 *
 * 实现支持下列接口的「快照数组」- SnapshotArray：
 * 
 * 
 * SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
 * void set(index, val) - 会将指定索引 index 处的元素设置为 val。
 * int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
 * int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。
 * 
 * 
 * 
 * 
 * ## 示例：
 * 
 * - 输入：["SnapshotArray","set","snap","set","get"]
 * ⁠    [[3],[0,5],[],[0,6],[0,0]]
 * - 输出：[null,null,0,null,5]
 * - 解释：
 * SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
 * snapshotArr.set(0,5);  // 令 array[0] = 5
 * snapshotArr.snap();  // 获取快照，返回 snap_id = 0
 * snapshotArr.set(0,6);
 * snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
 * 
 * 
 * 
 * ## 提示：
 *
 * - 1 <= length <= 50000
 * - 题目最多进行50000 次set，snap，和 get的调用 。
 * - 0 <= index < length
 * - 0 <= snap_id < 我们调用 snap() 的总次数
 * - 0 <= val <= 10^9
 * 
 */

// @lc code=start
use std::collections::BTreeMap;

/// ## 解题思路
/// - 数组+BTreeMap
struct SnapshotArray {
    data: Vec<BTreeMap<i32, i32>>,  // idx, snap_id -> val
    size: usize,  // data size
    snap_id: i32, // snap id
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl SnapshotArray {

    fn new(length: i32) -> Self {
        Self {
            size: length as usize,
            snap_id: 0,
            data: vec![BTreeMap::new(); length as usize],
        }
    }
    
    fn set(&mut self, index: i32, val: i32) {
        assert!(index < self.size as i32);

        self.data.get_mut(index as usize)
            .unwrap()
            .insert(self.snap_id, val);
    }
    
    fn snap(&mut self) -> i32 {
        self.snap_id += 1;
        self.snap_id - 1
    }
    
    fn get(&self, index: i32, snap_id: i32) -> i32 {
        assert!(snap_id <= self.snap_id);

        *self.data.get(index as usize)
            .unwrap()
            .range(..=snap_id)
            .last()
            .unwrap_or((&0, &0))
            .1
    }
}

// /**
//  * Your SnapshotArray object will be instantiated and called as such:
//  * let obj = SnapshotArray::new(length);
//  * obj.set(index, val);
//  * let ret_2: i32 = obj.snap();
//  * let ret_3: i32 = obj.get(index, snap_id);
//  */
// @lc code=end

